//给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '*',
// '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值24。 
//
// 你须遵守以下规则: 
//
// 
// 除法运算符 '/' 表示实数除法，而不是整数除法。
//
// 
// 例如， 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。 
// 
// 
// 每个运算都在两个数字之间。特别是，不能使用 “-” 作为一元运算符。
// 
// 例如，如果 cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。 
// 
// 
// 你不能把数字串在一起
// 
// 例如，如果 cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。 
// 
// 
// 
//
// 如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false 。 
//
// 
//
// 示例 1: 
//
// 
//输入: cards = [4, 1, 8, 7]
//输出: true
//解释: (8-4) * (7-1) = 24
// 
//
// 示例 2: 
//
// 
//输入: cards = [1, 2, 1, 2]
//输出: false
// 
//
// 
//
// 提示: 
//
// 
// cards.length == 4 
// 1 <= cards[i] <= 9 
// 
// Related Topics 数组 数学 回溯 👍 368 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class _679_Two4Game {
    public static void main(String[] args) {
        Solution solution = new _679_Two4Game().new Solution();
        int[] cards = {1,2,1,2};
        System.out.println(solution.judgePoint24(cards));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private static final int ADD = 0;
        private static final int SUB = 1;
        private static final int MUL = 2;
        private static final int DIV = 3;

        private static final double EPSILON = 1e-6;

        public boolean judgePoint24(int[] cards) {

            List<Double> list = new ArrayList<>();
            for (int card : cards) {
                list.add((double) card);
            }

            return solve(list);
        }

        private boolean solve(List<Double> list) {
            int size = list.size();
            if (size == 0) return false;
            if (size == 1) {
                if (Math.abs(list.get(0) - 24) < EPSILON) return true;
                else return false;
            }
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    if (i == j) continue;
                    List<Double> list2 = new ArrayList<>();
                    for (int k = 0; k < size; k++) {
                        if (k != i && k != j) list2.add(list.get(k));
                    }
                    for (int k = 0; k < 4; k++) {
                        if (i > j && (k == ADD || k == MUL)) continue;
                        if (k == ADD) {
                            list2.add(list.get(i) + list.get(j));
                        } else if (k == SUB) {
                            list2.add(list.get(i) - list.get(j));
                        } else if (k == MUL) {
                            list2.add(list.get(i) * list.get(j));
                        } else if (k == DIV) {
                            if (Math.abs(list.get(j)) < EPSILON) continue;
                            else list2.add(list.get(i) / list.get(j));
                        }
                        if (solve(list2)) {
                            return true;
                        }
                        list2.remove(list2.size() - 1);
                    }
                }
            }
            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}